package offer;

import java.util.List;

/**
 * @Author Elephas
 * @Date 2022/1/20
 **/
public class PreOrder {
    public static void main(String[] args) {

    }

    public void RecPreOrder(List<Integer> ans, TreeNode root){
        if(root == null){
            return;
        }else{
            ans.add(root.left.val);
            RecPreOrder(ans,root.left);
            RecPreOrder(ans,root.right);
        }
    }

    public void MorrisPreOrder(List<Integer> ans, TreeNode root){
        if(root == null){
            return;
        }
        TreeNode rightmost,current;
        current = root;
        while(current != null){
            if(current.left == null){
                ans.add(current.val);
                current = current.right;
            }else{
                rightmost = current.left;
                while(rightmost.right != null && rightmost.right != current ){
                    rightmost = rightmost.right;
                }
                if(rightmost.right == null){
                    ans.add(current.val);
                    rightmost.right = current;
                    current = current.left;
                }else{
                    rightmost.right = null;
                    current = current.right;
                }
            }
        }
    }
}
